package main

import (
	"fmt"
	"log"
	"os"
	"strconv"
)

/*
This function implements the Lomuto partition scheme.
The last element of the list is taken as a pivot and all the minor elements of the pivot are moved to the left,
while the larger ones to the right
*/
func partition(array []int, start int, end int) int {
	// Takes the last element
	pivot := array[end]

	i := (start - 1)

	for j := start; j < end; j++ {
		// If the value is lower than the pivot it moves to the left
		if array[j] < pivot {
			i++
			array[i], array[j] = array[j], array[i]
		}
	}
	// The pivot is moved to the "center" of the array where on the left are all the lowest values ​​and on the right the largest ones
	array[i+1], array[end] = array[end], array[i+1]

	return i + 1
}

func sort(array []int, start int, end int) []int {
	if start < end {
		pivotIndex := partition(array, start, end)
		// Sort the elements on the left of pivot
		sort(array, start, pivotIndex-1)
		// Sort the elements on the right of pivot
		sort(array, pivotIndex+1, end)
	}
	return array
}

func main() {
	var array []int

	// Converts all input arguments to integers and adds them to the list to be sorted
	for _, value := range os.Args[1:] {
		number, err := strconv.Atoi(value)

		if err != nil {
			log.Fatal(err)
		}

		array = append(array, number)
	}

	fmt.Println("Unsorted array => ", array)
	fmt.Println("Sorted array => ", sort(array, 0, len(array)-1))
}

/*
I => 4 23 5 1 1 48 993 -2 3 5 44 134234 343 324 -2314 -34 423
O => -2314 -34 -2 1 1 3 4 5 5 23 44 48 324 343 423 993 134234

Time complexity: O(n^2)     // Worst-case
				 O(n log n) // Best-case and Avarage

Space complexity: O(n) // If you consider the space that will be taken up by the call stack, generated by recursion
				  O(1) // If you ignore the call stack, no additional space is used
*/
